package com.foxzzz.greedy;


public class Solution321 {

    private int findMax(int start, int end, int[] num) {
        int index = start;
        end = end > num.length ? num.length : end;
        for (int i = start; i < end; i++) {
            if (num[i] == 9) {
                return i;
            } else if (num[i] > num[index]) {
                index = i;
            }
        }
        return index;
    }

    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] res = new int[k];
        int start1 = 0;
        int start2 = 0;
        for (int i = 0; i < k; i++) {
            int end1 = nums1.length + (nums2.length - start2) - k + i + 1;

            int end2 = nums2.length + (nums1.length - start1) - k + i + 1;

            int n1 = findMax(start1, end1, nums1);
            int n2 = findMax(start2, end2, nums2);

            if (n1 < nums1.length && nums1[n1] > nums2[n2]) {
                res[i] = nums1[n1];
                start1 = n1 + 1;
            } else if (n2 < nums2.length) {
                res[i] = nums2[n2];
                start2 = n2 + 1;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        new Solution321().maxNumber(new int[]{3,9}, new int[]{8,9}, 3);
        new Solution321().maxNumber(new int[]{6,7}, new int[]{6,0,4}, 5);
        new Solution321().maxNumber(new int[]{3, 4, 6, 5}, new int[]{9, 1, 2, 5, 8, 3}, 5);
    }
}
